package offer;



/**
 * @author zhanb
 * @date 2020/5/18
 */
public class Solution22 {

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        ListNode head = new ListNode(arr);
        System.out.println(getLength(head));
        System.out.println(getKthFromEnd2(head, 2));
    }

    /**
     * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，
     * 本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，
     * 它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
     *
     * 给定一个链表: 1->2->3->4->5, 和 k = 2.
     *
     * 返回链表 4->5.
     * @param head
     * @param k
     * @return
     */
    public static ListNode getKthFromEnd(ListNode head, int k) {
        if (head==null){
            return null;
        }
        int size =getLength(head);
        if(k <=0 || k > size) {
            return null;
        }
        //定义给辅助变量， for 循环定位到倒数的index
        //3 // 3 - 1 = 2
        ListNode cur = head;
        for(int i =0; i< size - k; i++) {
            cur = cur.next;
        }
        return cur;
    }

    public static int getLength(ListNode head){
        if(head==null){
            return 0;
        }
        int length=0;
        ListNode temp = head;
        while (temp!=null){
            length++;
            temp=temp.next;
        }
        return length;
    }

    /**
     * 初始化： 前指针 former 、后指针 latter ，双指针都指向头节点 head​ 。
     * 构建双指针距离： 前指针 former 先向前走 kk 步（结束后，双指针 former 和 latter 间相距 kk 步）。
     * 双指针共同移动： 循环中，双指针 former 和 latter 每轮都向前走一步，直至 former 走过链表 尾节点 时跳出（跳出后， latter 与尾节点距离为 k-1k−1，即 latter 指向倒数第 kk 个节点）。
     * 返回值： 返回 latter 即可。

     * @param head
     * @param k
     * @return
     */
    public static ListNode getKthFromEnd2(ListNode head, int k) {
        //快指针
        ListNode former = head;
        //慢指针
        ListNode latter = head;
        for(int i = 0; i < k; i++) {
            former = former.next;
        }
        //快指针走到最后节点的下一个为null
        while(former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }

    /**
     * 快慢指针
     * 加t代替第一个for循环
     * @param head
     * @param k
     * @return
     */
    public ListNode getKthFromEnd3(ListNode head, int k) {
        ListNode slow=head;
        ListNode fast=head;
        int t = 0;
        while(fast!=null){
            if(t>=k) {
                slow=slow.next;
            }
            fast = fast.next;
            t++;
        }
        return slow;
    }
}
